package primary.code06_graph;

/**
 * 前缀树，搜索具有某个前缀的字符串数量
 * 节点保存经过该节点的数量pass，以该节点结尾的数量end；
 * 节点保存边（字符）及该边通向的节点
 */
public class Code08_Trie {

    /**
     * 向前缀树添加字符串数组
     *
     * @param strs 字符串数组
     * @param root 前缀树
     */
    private static void addStrs(String[] strs, TrieNode root) {
        if (root == null) {
            root = new TrieNode();
        }
        if (strs == null || strs.length == 0) {
            return;
        }
        for (String str : strs) {
            TrieNode cur = root;
            //空字符串开头的数量
            cur.pass++;
            char[] chars = str.toCharArray();
            for (char aChar : chars) {
                //判断是否存在前往 achar 的路径
                if (cur.next[aChar - 'a'] == null) {
                    cur.next[aChar - 'a'] = new TrieNode();
                }
                cur = cur.next[aChar - 'a'];
                cur.pass++;
            }
            //结尾字符串数量
            cur.end++;
        }
    }

    /**
     * =====添加字符串=====
     * 将字符串分解为字符数组
     * 当前节点来到根节点
     * 当前节点pass++
     * while 字符数组未超出边界
     *      取下一字符
     *      当前节点中，该字符所对应的边是否有节点，无则新建节点
     *      当前节点指向字符所对应的边的节点
     *      当前节点pass++
     * end
     * 当前节点 end++
     * @param strs
     * @param root
     */
    private static void addStrsTest(String[] strs, TrieNode root) {
        if (root == null || strs == null || strs.length == 0) return;
        for (String str : strs) {
            if (str == null || str.length() == 0) continue;
            char[] chars = str.toCharArray();
            TrieNode cur = root;
            cur.pass++;
            int index = 0;
            while (index < chars.length) {
                char ch = chars[index++];
                TrieNode nextNode = cur.next[ch - 'a'];
                if (nextNode == null) {
                    nextNode = new TrieNode();
                    cur.next[ch - 'a'] = nextNode;
                }
                cur = nextNode;
                cur.pass++;
            }
            cur.end++;
        }
    }

    /**
     * 搜索是否存在某字符串
     *
     * @param str
     * @param root
     * @return
     */
    private static boolean searchString(String str, TrieNode root) {
        if (str == null || root == null) {
            return false;
        }
        char[] chars = str.toCharArray();
        TrieNode cur = root;
        for (char aChar : chars) {
            if (cur.next[aChar - 'a'] == null) {
                return false;
            }
            cur = cur.next[aChar - 'a'];
        }
        return true;
    }

    /**
     * =====搜索完整字符串=====
     * 将字符串分解为字符数组
     * 当前节点来到根节点
     * while 字符数组未超出边界
     *      取下一字符
     *      当前节点中，该字符所对应的边是否有节点，无则直接返回0
     *      当前节点指向字符所对应的边的节点
     * end
     * 返回 当前节点 end
     * @param str
     * @param root
     * @return
     */
    private static int searchStringTest(String str, TrieNode root) {
        if (root == null || str == null || str.length() == 0) return 0;
        char[] chars = str.toCharArray();
        TrieNode cur = root;
        int index = 0;
        while (index < chars.length) {
                char ch = chars[index++];
                TrieNode nextNode = cur.next[ch - 'a'];
                if (nextNode == null) return 0;
                cur = nextNode;
        }
        return cur.end;
    }

    /**
     * 删除一个字符串
     *
     * @param str
     * @param root
     */
    private static boolean deleteStr(String str, TrieNode root) {
        //前缀树中不包含有该字符串则直接返回
        if (str == null || root == null || !searchString(str, root)) {
            return false;
        }
        final char[] chars = str.toCharArray();
        TrieNode cur = root;
        TrieNode pre = null;
        cur.pass--;
        for (char aChar : chars) {
            pre = cur;
            cur = cur.next[aChar - 'a'];
            cur.pass--;
            //删除节点，结束
            if (cur.pass == 0) {
                pre.next[aChar - 'a'] = null;
                return true;
            }
        }
        cur.end--;
        return true;
    }

    /**
     * =====删除字符串=====
     * 搜索完整字符串，不存在则返回
     * 将字符串分解为字符数组
     * 当前节点来到根节点
     * 当前节点pass--
     * while 字符数组未超出边界
     *      取下一字符
     *      记录前节点
     *      当前节点指向字符所对应的边的节点
     *      当前节点pass--，如果pass减为0，则前节点断连当前节点
     * end
     * 当前节点 end--
     * @param str
     * @param root
     * @return
     */
    private static boolean deleteStrTest(String str, TrieNode root) {
        int count = searchStringTest(str, root);
        if (count < 1) return false;
        char[] chars = str.toCharArray();
        TrieNode cur = root;
        cur.pass--;
        int index = 0;
        while (index < chars.length) {
            char ch = chars[index++];
            TrieNode pre = cur;
            cur = cur.next[ch - 'a'];
            cur.pass--;
            if (cur.pass == 0) pre.next[ch - 'a'] = null;
        }
        cur.end--;
        return true;
    }

    /**
     * 查询 prefix 为前缀的数量
     *
     * @param prefix
     * @param root
     * @return
     */
    private static int samePrefixStrCount(String prefix, TrieNode root) {
        if (prefix == null || root == null) {
            return 0;
        }
        final char[] chars = prefix.toCharArray();
        TrieNode cur = root;
        for (char aChar : chars) {
            //不存在这样前缀的字符串
            if (cur.next[aChar - 'a'] == null) {
                return 0;
            }
            cur = cur.next[aChar - 'a'];
        }
        return cur.pass;
    }


    /**
     * =====搜索前缀字符串=====
     * 将字符串分解为字符数组
     * 当前节点来到根节点
     * while 字符数组未超出边界
     *      取下一字符
     *      当前节点中，该字符所对应的边是否有节点，无则直接返回0
     *      当前节点指向字符所对应的边的节点
     * end
     * 返回 当前节点 pass
     * @param prefix
     * @param root
     * @return
     */
    private static int samePrefixStrCountTest(String prefix, TrieNode root) {
        if (root == null || prefix == null || prefix.length() == 0) return 0;
        char[] chars = prefix.toCharArray();
        TrieNode cur = root;
        int index = 0;
        while (index < chars.length) {
            char ch = chars[index++];
            TrieNode nextNode = cur.next[ch - 'a'];
            if (nextNode == null) return 0;
            cur = nextNode;
        }
        return cur.pass;
    }

    //具有 ab 前缀的字符串数量:2
    //查询是否存在 abce :true
    //删除 abce
    //再次查询是否存在 abce :false
    public static void main(String[] args) {
        TrieNode root = new TrieNode();
        String[] strs = {"abce", "abd", "ace"};
        addStrs(strs, root);
        System.out.println("具有 ab 前缀的字符串数量:" + samePrefixStrCount("ab", root));
        System.out.println("查询是否存在 abce :" + searchString("abce", root));
        System.out.println("删除 abce");
        deleteStr("abce", root);
        System.out.println("再次查询是否存在 abce :" + searchString("abce", root));
    }

    public static void main2(String[] args) {
        TrieNode root = new TrieNode();
        String[] strs = {"abce", "abd", "ace"};
        addStrsTest(strs, root);
        System.out.println("具有 ab 前缀的字符串数量:" + samePrefixStrCountTest("ab", root));
        System.out.println("查询是否存在 abce :" + searchStringTest("abce", root));
        System.out.println("删除 abce");
        deleteStrTest("abce", root);
        System.out.println("再次查询是否存在 abce :" + searchStringTest("abce", root));
    }
}
